from typing import List
"""
        给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。
        机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。
        机器人每次只能向下或者向右移动一步。
        网格中的障碍物和空位置分别用 1 和 0 来表示。
        机器人的移动路径中不能包含 任何 有障碍物的方格。
        返回机器人能够到达右下角的不同路径数量。
        测试用例保证答案小于等于 2 * 109。

        示例 1：
             
                输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
                输出：2
                解释：3x3 网格的正中间有一个障碍物。
                从左上角到右下角一共有 2 条不同的路径：
                1. 向右 -> 向右 -> 向下 -> 向下
                2. 向下 -> 向下 -> 向右 -> 向右 
"""

class Solution:
    def uniquePathsWithObstacles(self, obs: List[List[int]]) -> int:
        if obs[0][0] == 1 or obs[-1][-1] == 1:
            return 0
        fl = 1
        for i in range(len(obs)):
            if obs[i][0] != 1 and fl == 1:
                obs[i][0] = 1
            else:
                fl = 0
                obs[i][0] = 0
        fl = 1
        for i in range(1,len(obs[0])):
            if obs[0][i] != 1 and fl == 1:
                obs[0][i] = 1
            else:
                obs[0][i] = 0
                fl = 0

        for i in range(1,len(obs)):
            for j in range(1,len(obs[0])):
                if obs[i][j] == 1:
                    obs[i][j] = 0
                    continue
                else:
                    obs[i][j] = obs[i-1][j] + obs[i][j-1]
        return obs[-1][-1]
